package algo.sort;

public abstract class MergeSort<T extends Comparable<? super T>> extends Sort<T>{

    protected T[] aux;

    protected void merge(T[] nums, int left, int mid, int right) {
        // 如  1 3, 5, 7,      9,     2, 4, 6, 8, 10;
        // nums[mid] 是 9
        // nums[i] 从 1开始，    nums[j] 从 2开始
        // 我们开始挨个比较、合并：
        // 1, 3, 5, 7, 9
        // 2, 4, 6, 8, 10

        // 我们分别从两边的左端开始合并
        int i = left, j = mid + 1;

        for (int k=left; k<=right; ++k) {
            aux[k] = nums[k];
        }

        for (int k=left; k<=right; ++k) {

            // i > mid 意味着左边的数字全部使用了
            if (i > mid) {
                nums[k] = aux[j++];

            // j > right 意味着右边的数字全部使用了
            } else if (j > right) {
                nums[k] = aux[i++];

            // 当 nums[i] < nums[j]  ，选择nums[i]  否则选 nums[j]
            } else if (aux[i].compareTo(aux[j]) <= 0) {
                nums[k] = aux[i++];
            } else {
                nums[k] = aux[j++];
            }
        }
    }

    protected void mergeDesc(T[] nums, int left, int mid, int right) {
        int i = left, j = mid + 1;

        for (int k=left; k<=right; ++k) {
            aux[k] = nums[k];
        }

        for (int k=left; k<=right; ++k) {
            if (i > mid) {
                nums[k] = aux[j++];
            } else if (j > right) {
                nums[k] = aux[i++];
            } else if (aux[i].compareTo(aux[j]) >= 0) {
                nums[k] = aux[i++];
            } else {
                nums[k] = aux[j++];
            }
        }
    }
}
